The present application relates to a network architectures design, and more particularly to infrastructure wireless mesh networks with location tracking.
Background: Wireless Mesh Networks
There are two types of Wireless Mesh Networks (WMNs): infrastructure and ad hoc. This application focuses on infrastructure WMNs, which most enterprise applications will be based on. FIG. 2 shows an infrastructure WMN which consists of meshed access points (APs) and clients. APs' locations are fixed (not moving), but clients are mobile. The goal of a multi-hop WMN is to extend the 802.11 wireless LAN services to a much larger area without installing LAN cabling and other network infrastructures.
Unfortunately, a WMN has an intrinsic hidden- and exposed-terminal problem in a multi-hop environment which limits the scalability of the network. The RTS (Request-To-Send)/CTS (Clear-To-Send) collision avoidance method adopted by the 802 is believed to be ineffective in a multi-hop environment. It leads to a very low space reuse factor in a multi-hop environment.
The RTS/CTS efficiency is dominated by the following parameters.                Rt; Transmission range.        Ri: Interference range: the range within which stations in receive mode will be interfered by other transmitters and thus suffer a loss.        Rs: Carrier sense range: the range within which the power from the transmitter can be sensed, indicating the busy state of the medium.        
The relationship among these parameters is very complicated in real applications. For example, Ri depends on the distance between the sender and the receiver and its value varies for each transmission. The complicated relationship among these parameters explains why the RTS/CTS handshake cannot solve the hidden-terminal problem, nor the exposed-terminal problem.
FIG. 3A shows the Hidden-terminal Problem. In this example, A sends a packet to B, and C is outside the transmission range of B, but within the interference range. RTS/CTS cannot prevent a collision caused by transmissions from A and C. FIG. 3B shows the Exposed-Terminal Problem. In this example, B sends a packet to A, and later C intends to send a packet to D. Because B sends out a RTS and C receives it. So C will defer its transmission even though C can sends a packet to D which will not cause a collision (C is exposed from B—Inefficiency).
Several approaches have been proposed to improve the space re-use efficiency of the RTS/CTS scheme. One is to add two tones to the scheme—one controls transmission and one controls receiving The RTS/CTS controls both transmission and receiving channels). Another approach involves the use of power control. Yet another approach uses directional antennas, where every wireless node uses multiple antennas, each “tuned” to a specific portion (cone) of the three-dimensional space. Others have been proposed to dynamically adjust the Rs (sensing range) or Rt (transmission range). All these schemes share some common problems: (1) they add a significant complexity to the protocol, (2) it is difficult to make them compatible with 802.11 existing devices, and (3) it is unclear how effective they are in a real implementation because of the complicated relationship between Rt (transmission range), Ri (interference range) and Rs (sensing range).
Scalable Wireless Mesh Networks
The present application provides new methods to design scalable WMN networks. In various embodiments, a frequency planning scheme deploys orthogonal frequencies indefinitely for adjacent cells and consequently no interference occurs. Also, the proposed mobility tracking scheme requires no central database and can easily locate a mobile user in a network.
The disclosed inventions, in various embodiments, can provide some or all of the following advantages, among other:                Wireless Mesh Networks can avoid most of the hidden and exposed terminal problems of 802.11-based WMN networks, and offer a much higher capacity;        Wireless Mesh networks networks are compatible with existing WiFi devices.        A frequency planning scheme which generates no interference among adjacent cells.        A mobility tracking scheme does not require a central database and therefore is scalable.        The proposed architectures will not interrupt on-going flows in a network.        The proposed architectures offer transparent layer-2 interconnects and handoffs.        The proposed architectures support both unicast and broadcast, and        The proposed architectures make no assumptions about higher layers and can work with any layer-3 protocols.        